import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class FourSum {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        List<Integer> list = null;
        Arrays.sort(nums);
        int n = nums.length;
        for (int d = 0; d < n - 3; d++) {
            for (int c = d + 1; c < n - 2; c++) {
                long tSum = (long)target - (long)nums[d] - (long)nums[c];

                int left = c + 1, right = n - 1;
                while (left < right) {
                    long sum = nums[left] + nums[right];
                    if (sum < tSum) {
                        left++;
                    }else if(sum > tSum) {
                        right--;
                    }else {
                        list = new ArrayList<>();
                        list.add(nums[left]);
                        list.add(nums[right]);
                        list.add(nums[c]);
                        list.add(nums[d]);
                        ret.add(list);
                        while(nums[left+1] == nums[left] && left+1 < right) {
                            left++;
                        }
                        left++;
                        while(nums[right-1] == nums[right] && left < right-1) {
                            right--;
                        }
                        right--;
                    }
                }
                while(nums[c + 1] == nums[c] && c+1 < n-2) {
                    c++;
                }
            }
            while(nums[d+1] == nums[d] && d+1 < n-3) {
                d++;
            }
        }
        return ret;
    }
}
